package com.ashin.dp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Ashin
 * @Date: 2020/10/28
 * @Description: com.ashin.dp
 * @Version: 1.0.0
 */
public class Brackets {


    @Test
    public void test() {
        List<String> brackets = brackets(3);
        System.out.println(brackets);
    }

    /**
     * 有效的括号组合
     *
     * @param n
     * @return
     */
    private List<String> brackets(int n) {
        List<String> result = new ArrayList<>();

        brackets("", 0, 0, n, result);

        return result;
    }

    private void brackets(String cur, int left, int right, int n, List<String> resultList) {
        if (left + right == 2 * n) {
            resultList.add(cur);
            return;
        }

        if (left < n) {
            brackets(cur + "(", left + 1, right, n, resultList);
        }

        if (right < left) {
            brackets(cur + ")", left, right + 1, n, resultList);
        }
    }

}
